package com.cty.twentySecondDay;
/*
* 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
* 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
*
* */
public class Q_30 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        ListNode listNode = swapPairs(node1);
    }
    // 三指针 时间复杂度O(L) 空间复杂度O(1) 作者自己写的 经过调试终于过了 迭代
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        // 先创建一个哑节点
        ListNode dummy = new ListNode(0,head);
        ListNode prev = dummy;
        ListNode current = head;
        while (current != null && current.next != null) {
            ListNode next = current.next;
            current.next = next.next;
            prev.next = next;
            next.next = current;
            prev = prev.next.next;
            // 此时的current向前走了一步 所以current只需要向前走一步即可
            current = current.next;
        }
        return dummy.next;
    }

    // 力扣官方题解 方法一：递归
    /*
    * 思路:先利用递归 交换后面的元素 返回的是新的头节点
    *   每一次递归 都是将head和newHead交换位置 然后返回newHead
    *   让本次递归的head的next指向上一次递归的newHead 最后一次返回newHead
    *   时间复杂度O(n) 空间复杂度O(n)
    * */
    public static ListNode swapPairs2(ListNode head) {
        if(head == null || head.next == null) return head;
        //让新的头节点等于本次的头节点的下一个节点
        ListNode newHead = head.next;
        //键新节点的下一个节点作为头节点传进去 先交换后面的节点 然后将当前的头节点先跟后面的头节点建立连接
        head.next = swapPairs(newHead.next);
        // 在修改当前节点
        newHead.next = head;
        // 返回当前节点
        return newHead;
    }
}
